#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <string>
#include <sstream>
using namespace std;

class Solution {
public:
    string intToRoman(int num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function 
		ostringstream oss;

		int thousand = num / 1000;
		for(int i=0;i<thousand;i++)
			oss<<'M';

		int hundred = num / 100 % 10;
		genSymbol(hundred,'M','D','C',oss);

		int tens = num / 10 % 10;
		genSymbol(tens,'C','L','X',oss);

		int ones = num % 10;
		genSymbol(ones,'X','V','I',oss);
		
		return oss.str();
    }
private:
	void genSymbol(int num, char ten,char five,char one,ostringstream& oss)
	{
		if(0==num)
			return;
		if(9==num)
			oss<<one<<ten;
		else if(num > 5)
		{
			oss<<five;
			for(int i=0;i<(num-5);i++)
				oss<<one;
		}
		else if(5==num)
			oss<<five;
		else if(4==num)
		{
			oss<<one<<five;
		}
		else
		{
			while(num-->0)
				oss<<one;
		}
	}
};
#endif